#import "PriorityQueue.h"

// Copyright (C) 1993 by Don Yacktman

// To Do:  make sure that all List methods that add an object are overridden
// to make sure that added objects follow the protocol.  Note that I could
// also provide a default key (like use -hash) if the protocol isn't
// followed, but I doubt this would be particularly useful.  A given
// application for this object will know how it wants things sorted and
// will, therefore, implement the necessary method.


// Implementation note:  we keep the list organized as a heap, which allows
// us to do extremely fast searching and insertion.  The key point is that
// the heap structure will _always_ leave us with the next event in slot #1.

@interface PriorityQueue(private)

// utility methods that shouldn't be called or modified by you.  :-)
- _swapObjectsAt:(int)index1 and:(int)index2;
- _heapify:(int)node;

@end

@implementation PriorityQueue(private)

- _swapObjectsAt:(unsigned int)index1 and:(unsigned int)index2
{	// right now only heapify uses this, so it could be folded into
	// it for speed.  This is easier to read, IMHO...
	[self replaceObjectAt:index2
		  with:[self replaceObjectAt:index1
					 with:[self objectAt:index2]]];
	return self;
}

- _heapify:(unsigned int)node
{
	unsigned int smallest = node;			// the current node's index
	unsigned int left = 2 * (node + 1) - 1;	// left child node's index
	unsigned int right = 2 * (node + 1);	// right child node's index
	unsigned int max = [self count];

	// find out which has the smaller key, parent, left child, or right child.
	// the smallest becomes the parent; if no change, we're done, but if we have
	// to move a node, then we will check the new child to make sure it's
	// children aren't smaller... so we recursively descend into the heap.
	if (left < max)
		if ([[self objectAt:left] sortKey] < [[self objectAt:smallest] sortKey])
			smallest = left;
	if (right < max)
		if ([[self objectAt:right] sortKey] < [[self objectAt:smallest] sortKey])
			smallest = right;
	if (smallest != node) { // left or right is smaller...
		[self _swapObjectsAt:node and:smallest];	// swap to keep sorted
		[self _heapify:smallest];	// propagate down the heap
	}
	return self;
}

@end

@implementation PriorityQueue

// we override to sort it as we go...
- addObject:anObject
{
	unsigned int i, newKey;
	if ([anObject conformsTo:@protocol()]) newKey = [anObject sortKey];
	else return nil;	// error, object can't be sorted without a key!
	[super addObject:anObject]; // make sure that we have dynamically
					// grown to the right size to fit the new object
	i = [self count]; // start at the bottom of the heap
	// All the "x - 1" in the while loop are 'cos the List starts at
	// index zero and the heap algorithm want us to used start index=1
	while ((i > 1) && ([[self objectAt:((i/2) - 1)] sortKey] > newKey)) {
		// shift object to bottom of heap if they have larger keys
		// so that we'll have room to insert our new object
		[self replaceObjectAt:(i-1) with:[self objectAt:((i/2)-1)]];
		i /= 2; // heap is a binary tree, implemented in a linear array;
		// dividing by two always gives the parent node...
	}
	// insert the new object in the right place
	[self replaceObjectAt:(i-1) with:anObject];
	return self;
}

- removeNextObject
{
	id ret = [self objectAt:0];
	// put the last object in the heap at the top
	[self replaceObjectAt:0 with:[self lastObject]];
	// get rid of the duplicate we just created
	[self removeLastObject];
	// and then propagate it to the bottom of the heap
	[self _heapify:0];
	return ret;
}

@end

